This invention relates to an entropy encoder for use in a high speed data transmission system, and more particularly to a variable-length codeword encoder.
Variable-length coding is a coding technique often used for lossless data compression. In accordance with this technique, fixed-length data is converted into variable-length codewords according to the statistics of the data. In general, the lengths of the codewords are chosen so that shorter codewords are used to represent the more frequently occurring data and longer codewords are chosen to represent the less frequently occurring data. By properly assigning the variable-length codewords to the library of all possible source codewords, the average word length of the variable-length code is shorter than that of the original data and, therefore, data compression is achieved. Huffman code design is a procedure commonly used to construct a minimum redundant variable-length code for a known data statistic. Generally, the encoding process can be implemented by a table-lookup process using the input data to address the table. The codewords and word-lengths are stored as table contents. Each fixed-length input symbol word is coded, at a sample clock rate, into the variable-length codeword it is associated with in the table, and the associated table codeword lengths are used to control circuitry to bit-by-bit concatenate the successive variable-length codewords into a bit stream. The bit stream is then divided into fixed-length data segments and stored in a buffer and then outputted sequentially at either a fixed or a variable rate for transmission over a data channel. At the receiving end, a buffer generally stores the received bit stream in fixed-length segments and retrieves these segments to form a continuous stream from which each variable-length codeword is successively decoded, at the fixed sample clock rate, back into its original source symbol.
Both the encoding and decoding of variable-length codewords are difficult at high speeds. Generally, during each symbol period in both the encoder and decoder all the bits in a variable-length codeword may need to be shifted through a register at a rate substantially greater than the sample clock rate. Speed requirements are a particular critical concern in the digital transmission of high definition (HDTV) signals. In such an HDTV system the total sample rate (combining luminance and chrominance signals) is likely to be 100 MHz. If variable-length coding is used, the maximum length codeword could typically be 16 bits. In the worst case, therefore, an encoder or decoder would need to shift bits through a register at 16 times the sample rate, or at 1.6 G bits/sec, to code or decode words at the sample rate. Such high speeds are very difficult to implement using current IC technology.
The problem of high-speed decoding in a variable-length decoder is approached in co-pending patent application, Ser. No. 546,415, filed Jun. 29, 1990, co-invented by two of the co-inventors herein. That decoder includes two cascaded latch circuits, each having a bit capacity equal to the maximum codeword length and which store consecutive bits supplied from an input buffer memory which stores the stream to be decoded in fixed-length data segments; a barrel shifter, which is input from the two latch circuits and which provides a sliding decoding window output equal in length to the maximum codeword length; an accumulator which accumulates, modulo the maximum codeword length, the lengths of the sequentially decoded variable-length codewords; and a table-lookup memory device, which outputs, for an input sequence of bits that begins with the first bit of a variable-length codeword, a fixed-length word corresponding to that variable-length codeword and that variable-length codeword length. As a codeword is decoded during each clock cycle, its length is accumulated and the decoding window of the barrel shifter is directly shifted to begin with the first bit of the next to-be-decoded codeword. When, during a clock cycle, the accumulated lengths exceeds the maximum codeword length, which indicates that all the bits in the first latch circuit have been decoded, the bits in the second latch are transferred into the first latch and the next fixed-length data-segment of bits is read into the second latch from the buffer memory. With this decoder, a continuous stream of bits from the buffer is always at-the-ready to be decoded and the variable-length codewords can be decoded at the sample clock rate without the necessity of clocking bits at a very high bit rate.
As aforenoted, at the transmitting end of a high-speed data transmission system, a similar problem needs to be solved in order to code each symbol at the sample clock rate without needing to shift bits at a higher rate. Although at a high level of understanding, the problem of coding and decoding are conceptually related, in actuality the problems associated with the coding and decoding of variable-length codewords are dissimilar. Whereas the problem in the decoder is to determine, from an already existing continuous stream of variable-length words, the end of each successive word and then shift to the next word in a single clock cycle, the encoder oppositely must form the continuous stream from successive words that arrive a constant rate but with a variable number of bits. Thus, the encoder must concatenate each successive word with a previous one in a single clock cycle. Furthermore, the concatenated stream needs to be divided into fixed-length segments to be stored in a buffer for later accessing for transmission over the data channel at either a fixed or variable bit rate.
An object of the present invention is to code input symbols into variable-length codewords at a sample clock rate, to concatenate, at each clock cycle, the resultant variable-length codewords into a stream, and to output to a buffer fixed-length segments of the concatenated stream as that fixed number of bits are accumulated.